package com.hot100.t1;

/**
 * @Author Zan
 * @Create 2024/7/27 22:11
 * @ClassName: Test
 * @Description : 160. 相交链表
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envType=problem-list-v2&envId=2cktkvj
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) { // 初始化链表
        this.val = x;
        this.next = null;
    }
}

public class Test {
    public static void main(String[] args) {

    }
}

class Solution {
    /**
     * 思路展现：
     * 1. 两个链表的长度是不同的，但是有一点可以肯定的是 A + B = B + A
     * 2. 所以当一个走到结尾的时候，去走另一个走的路，那最后他们两个走的路都是A + B，因此是相同的
     * 3. 既然相同，那就可以看到当两个走到第一个相同节点的时候，就是相交节点
     * 时间复杂度：O(n)
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果为空，那就说明是null，肯定没有相交节点
        if (headA == null || headB == null)
            return null;

        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            // 两边进行向后走，如果为null，那就走另一半的路
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}



